//
// C++ Interface: LinkedList
//
// Description: 
//
//
// Author: James Molloy <james@jamesmolloy.co.uk>, (C) 2007
//
// Copyright: See COPYING file that comes with this distribution
//
//
#ifndef LINKEDLIST_H
#define LINKEDLIST_H

#include <jimix/Globals.h>

/**
  Implements a templated singly-linked-list.
**/
template <class T>
class LinkedList
{
public:
  LinkedList() :
    listHead(NULL),
    listTail(NULL),
    length(0)
  {}

  ~LinkedList()
  {}
  
  /**
    Inserts val at the start of the list.
  **/
  void insertFirst(T val)
  {
    listHead = new ListNode(val, listHead);
    if (listTail == NULL)
    {
      listTail = listHead;
    }
    length++;
  }
  
  /**
    Inserts val at the end of the list.
  **/
  void insertLast(T val)
  {
    if (!listTail)
    {
      insertFirst(val);
    }
    else
    {
      listTail->next = new ListNode(val, NULL);
      listTail = listTail->next;
      length++;
    }
  }
  
  /**
    Removes and returns the value from the front of the list.
    Delete is NOT called on the datum.
  **/
  T removeFirst()
  {
    T toRet = (T)0;
    if (listHead)
    {
      ListNode *tmp = listHead;
      listHead = listHead->next;
      if (listHead == NULL)
      {
        listTail = NULL;
      }
      length--;
      toRet = tmp->datum;
      delete tmp;
    }
    return toRet;
  }
  
  /**
    Returns the number of items in the list.
  **/
  u32int getLength()
  {
    return length;
  }
  
  /**
    Returns the head of the list.
  **/
  T getFirst()
  {
    if (listHead)
    {
      return listHead->datum;
    }
    else
    {
      return (T)NULL;
    }
  }
  
  /**
    Sets the internal iterator to point to the first item in the list,
    and returns that item. Returns NULL if list empty.
  **/
  T iterateFirst()
  {
    iterator = listHead;
    if (listHead)
    {
      return listHead->datum;
    }
    else
    {
      return (T)NULL;
    }
  }
  
  /**
    Increments the internal iterator and returns that item. Returns
    NULL if list empty.
  **/
  T iterateNext()
  {
    if (!iterator)
    {
      return (T)NULL;
    }
    iterator = iterator->next;
    if (iterator)
    {
      return iterator->datum;
    }
    else
    {
      return (T)NULL;
    }
  }
  
  /**
    Decrements the internal iterator and returns that item. Returns 
    NULL if list empty. This operates in O(n) time! beware!
  **/
  T iteratePrev()
  {
    if (!iterator ||
        iterator == listHead)
    {
      return (T)NULL;
    }
    ListNode *search = iterator;
    iterator = listHead;
    while (iterator->next != search)
    {
      iterator = iterator->next;
    }
    return iterator->datum;
  }
  
  /**
    Returns true if the internal iterator is pointing at a valid
    node.
  **/
  bool iterateIsValid()
  {
    return (iterator != NULL);
  }

  /**
    Returns the value at the current iterator position.
  **/
  T iterateGetValue()
  {
    if (iterator)
    {
      return iterator->datum;
    }
    else
    {
      return (T)NULL;
    }
  }
  
  /**
    Removes the item at the current iterator position.
  **/
  void remove()
  {
    if (iterator)
    {
      if (iterator == listHead)
      {
        removeFirst();
        iterator = listHead;
      }
      else
      {
        ListNode *beforeIterator = listHead;
        while (beforeIterator->next != iterator)
        {
          beforeIterator = beforeIterator->next;
        }
        if (iterator == listTail)
        {
          listTail = beforeIterator;
          listTail->next = NULL;
          delete iterator;
          iterator = NULL;
        }
        else
        {
          beforeIterator->next = iterator->next;
          delete iterator;
          iterator = beforeIterator->next;
        }
        length --;
      }
    }
  }
  
private:

  class ListNode
  {
  public:
    ListNode(T datum, class ListNode *next) :
     datum(datum), next(next) {}
    ~ListNode() {}
    
    T datum;
    class ListNode *next;
  };

  /**
    The head node of this linked list.
  **/
  ListNode *listHead;

  /**
    The tail node of this linked list.
  **/
  ListNode *listTail;
  
  /**
    The length of the list.
  **/
  u32int length;

  /**
    An internal iterator to help us cycle through the list.
  **/
  ListNode *iterator;
  
};

#endif
